package Leetcode.每日一题;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @ClassName 环形子数组的最大和
 * @since: 2023/7/20 21:42
 * @auth: kirito
 * @description:
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ，
nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，
不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
 *
 * 自己的思路：知道i位置的前面和后面的数字的表达式，那就直接3层循环算n次n数组的最大和 时间复杂度o(n*n*n)
 * 两层求当前数组的最大和 最长公共子序列同理 但是忘了，，，
 *
 * https://leetcode.cn/problems/maximum-sum-circular-subarray/solution/huan-xing-zi-shu-zu-de-zui-da-he-by-leet-elou/
 * 1.不拆  中间部分最大和
 *   拆  左大 + 右大
 * 2.队列，在复制一份放在队尾，相当于2n中去找n的最大值
 **/
public class 环形子数组的最大和 {
    public static int maxSubarraySumCircular(int[] nums) {
            int n = nums.length;
            int[] leftMax = new int[n];
            // 对坐标为 0 处的元素单独处理，避免考虑子数组为空的情况
            leftMax[0] = nums[0];
            int leftSum = nums[0];
            int pre = nums[0];
            int res = nums[0];
            for (int i = 1; i < n; i++) {
                pre = Math.max(pre + nums[i], nums[i]);
                res = Math.max(res, pre);
                leftSum += nums[i];
                leftMax[i] = Math.max(leftMax[i - 1], leftSum);
            }

            // 从右到左枚举后缀，固定后缀，选择最大前缀
            int rightSum = 0;
            for (int i = n - 1; i > 0; i--) {
                rightSum += nums[i];
                res = Math.max(res, rightSum + leftMax[i - 1]);
            }
            return res;
    }
    public int maxSubarraySumCircular2(int[] nums) {
        int n = nums.length;
        Deque<int[]> queue = new ArrayDeque<int[]>();
        int pre = nums[0], res = nums[0];
        queue.offerLast(new int[]{0, pre});
        for (int i = 1; i < 2 * n; i++) {
            while (!queue.isEmpty() && queue.peekFirst()[0] < i - n) {
                queue.pollFirst();
            }
            pre += nums[i % n];
            res = Math.max(res, pre - queue.peekFirst()[1]);
            while (!queue.isEmpty() && queue.peekLast()[1] >= pre) {
                queue.pollLast();
            }
            queue.offerLast(new int[]{i, pre});
        }
        return res;
    }



}
